<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 5.4</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 5.4" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 5.4" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-5.xhtml#Chapter-5" rel="prev" title="Chapter 5" />
<link href="5_002e5.xhtml#g_t5_002e5" rel="next" title="5.5" />
<link href="5_002e3.xhtml#g_t5_002e3_002e2" rel="prev" title="5.3.2" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t5_002e4"></a>
<nav class="header">
<p>
Next: <a href="5_002e5.xhtml#g_t5_002e5" accesskey="n" rel="next">5.5</a>, Prev: <a href="5_002e3.xhtml#g_t5_002e3" accesskey="p" rel="prev">5.3</a>, Up: <a href="Chapter-5.xhtml#Chapter-5" accesskey="u" rel="prev">Chapter 5</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="The-Explicit_002dControl-Evaluator"></a>
<h3 class="section"><span class="secnum">5.4</span><span class="sectitle">The Explicit-Control Evaluator</span></h3>

<p>In <a href="5_002e1.xhtml#g_t5_002e1">5.1</a> we saw how to transform simple Scheme programs into
descriptions of register machines.  We will now perform this transformation on
a more complex program, the metacircular evaluator of 
<a href="4_002e1.xhtml#g_t4_002e1_002e1">4.1.1</a>–<a href="4_002e1.xhtml#g_t4_002e1_002e4">4.1.4</a>, which shows how the behavior of a Scheme interpreter
can be described in terms of the procedures <code>eval</code> and <code>apply</code>. The
<a id="index-explicit_002dcontrol-evaluator"></a>
<em>explicit-control evaluator</em> that we develop in this section shows how
the underlying procedure-calling and argument-passing mechanisms used in the
evaluation process can be described in terms of operations on registers and
stacks.  In addition, the explicit-control evaluator can serve as an
implementation of a Scheme interpreter, written in a language that is very
similar to the native machine language of conventional computers.  The
evaluator can be executed by the register-machine simulator of 
<a href="5_002e2.xhtml#g_t5_002e2">5.2</a>.  Alternatively, it can be used as a starting point for building a
machine-language implementation of a Scheme evaluator, or even a
special-purpose machine for evaluating Scheme expressions.  <a href="#Figure-5_002e16">Figure 5.16</a>
shows such a hardware implementation: a silicon chip that acts as an evaluator
for Scheme.  The chip designers started with the data-path and controller
specifications for a register machine similar to the evaluator described in
this section and used design automation programs to construct the
integrated-circuit layout.<a class="footnote_link" id="DOCF304" href="#FOOT304"><sup>304</sup></a>
</p>
<figure class="float">
<a id="Figure-5_002e16"></a>
<object style="width: 52.41ex; height: 42.31ex;" data="fig/chap5/chip.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 5.16:</strong> A silicon-chip implementation of an evaluator for Scheme.</p>
</figcaption>
</figure>

<a id="Registers-and-operations"></a>
<h5 class="subsubheading">Registers and operations</h5>

<p>In designing the explicit-control evaluator, we must specify the operations to
be used in our register machine.  We described the metacircular evaluator in
terms of abstract syntax, using procedures such as <code>quoted?</code> and
<code>make-procedure</code>.  In implementing the register machine, we could expand
these procedures into sequences of elementary list-structure memory operations,
and implement these operations on our register machine.  However, this would
make our evaluator very long, obscuring the basic structure with details.  To
clarify the presentation, we will include as primitive operations of the
register machine the syntax procedures given in <a href="4_002e1.xhtml#g_t4_002e1_002e2">4.1.2</a> and the
procedures for representing environments and other run-time data given in
sections <a href="4_002e1.xhtml#g_t4_002e1_002e3">4.1.3</a> and <a href="4_002e1.xhtml#g_t4_002e1_002e4">4.1.4</a>.  In order to completely specify an
evaluator that could be programmed in a low-level machine language or
implemented in hardware, we would replace these operations by more elementary
operations, using the list-structure implementation we described in 
<a href="5_002e3.xhtml#g_t5_002e3">5.3</a>.
</p>
<p>Our Scheme evaluator register machine includes a stack and seven registers:
<code>exp</code>, <code>env</code>, <code>val</code>, <code>continue</code>, <code>proc</code>, <code>argl</code>,
and <code>unev</code>.  <code>Exp</code> is used to hold the expression to be evaluated,
and <code>env</code> contains the environment in which the evaluation is to be
performed.  At the end of an evaluation, <code>val</code> contains the value obtained
by evaluating the expression in the designated environment.  The
<code>continue</code> register is used to implement recursion, as explained in
<a href="5_002e1.xhtml#g_t5_002e1_002e4">5.1.4</a>.  (The evaluator needs to call itself recursively, since
evaluating an expression requires evaluating its subexpressions.)  The
registers <code>proc</code>, <code>argl</code>, and <code>unev</code> are used in evaluating
combinations.
</p>
<p>We will not provide a data-path diagram to show how the registers and
operations of the evaluator are connected, nor will we give the complete list
of machine operations.  These are implicit in the evaluator’s controller, which
will be presented in detail.
</p>

<a id="g_t5_002e4_002e1"></a>
<a id="The-Core-of-the-Explicit_002dControl-Evaluator"></a>
<h4 class="subsection"><span class="secnum">5.4.1</span><span class="sectitle">The Core of the Explicit-Control Evaluator</span></h4>

<p>The central element in the evaluator is the sequence of instructions beginning
at <code>eval-dispatch</code>.  This corresponds to the <code>eval</code> procedure of the
metacircular evaluator described in <a href="4_002e1.xhtml#g_t4_002e1_002e1">4.1.1</a>.  When the controller
starts at <code>eval-dispatch</code>, it evaluates the expression specified by
<code>exp</code> in the environment specified by <code>env</code>.  When evaluation is
complete, the controller will go to the entry point stored in <code>continue</code>,
and the <code>val</code> register will hold the value of the expression.  As with the
metacircular <code>eval</code>, the structure of <code>eval-dispatch</code> is a case
analysis on the syntactic type of the expression to be evaluated.<a class="footnote_link" id="DOCF305" href="#FOOT305"><sup>305</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">eval-dispatch
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op self-evaluating?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-self-eval</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op variable?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-variable</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op quoted?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-quoted</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op assignment?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-assignment</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op definition?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-definition</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">if</span><span class="pun">?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-if</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">lambda</span><span class="pun">?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-lambda</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="kwd">begin</span><span class="pun">?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-begin</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op application?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-application</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label unknown-expression-type</span><span class="clo">))</span></pre></div>

<a id="Evaluating-simple-expressions"></a>
<h5 class="subsubheading">Evaluating simple expressions</h5>

<p>Numbers and strings (which are self-evaluating), variables, quotations, and
<code>lambda</code> expressions have no subexpressions to be evaluated.  For these,
the evaluator simply places the correct value in the <code>val</code> register and
continues execution at the entry point specified by <code>continue</code>.
Evaluation of simple expressions is performed by the following controller code:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-self-eval
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span><span class="pln">
ev-variable
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op lookup-variable-value</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span><span class="pln">
ev-quoted
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">op text-of-quotation</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span><span class="pln">
ev-lambda
  </span><span class="opn">(</span><span class="pln">assign unev
          </span><span class="opn">(</span><span class="pln">op lambda-parameters</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign exp 
          </span><span class="opn">(</span><span class="pln">op lambda-body</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val 
          </span><span class="opn">(</span><span class="pln">op make-procedure</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span></pre></div>

<p>Observe how <code>ev-lambda</code> uses the <code>unev</code> and <code>exp</code> registers to
hold the parameters and body of the lambda expression so that they can be
passed to the <code>make-procedure</code> operation, along with the environment in
<code>env</code>.
</p>
<a id="Evaluating-procedure-applications"></a>
<h5 class="subsubheading">Evaluating procedure applications</h5>

<p>A procedure application is specified by a combination containing an operator
and operands.  The operator is a subexpression whose value is a procedure, and
the operands are subexpressions whose values are the arguments to which the
procedure should be applied.  The metacircular <code>eval</code> handles applications
by calling itself recursively to evaluate each element of the combination, and
then passing the results to <code>apply</code>, which performs the actual procedure
application.  The explicit-control evaluator does the same thing; these
recursive calls are implemented by <code>goto</code> instructions, together with use
of the stack to save registers that will be restored after the recursive call
returns.  Before each call we will be careful to identify which registers must
be saved (because their values will be needed later).<a class="footnote_link" id="DOCF306" href="#FOOT306"><sup>306</sup></a>
</p>
<p>We begin the evaluation of an application by evaluating the operator to produce
a procedure, which will later be applied to the evaluated operands.  To
evaluate the operator, we move it to the <code>exp</code> register and go to
<code>eval-dispatch</code>.  The environment in the <code>env</code> register is already
the correct one in which to evaluate the operator.  However, we save <code>env</code>
because we will need it later to evaluate the operands.  We also extract the
operands into <code>unev</code> and save this on the stack.  We set up
<code>continue</code> so that <code>eval-dispatch</code> will resume at
<code>ev-appl-did-operator</code> after the operator has been evaluated.  First,
however, we save the old value of <code>continue</code>, which tells the controller
where to continue after the application.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-application
  </span><span class="opn">(</span><span class="pln">save continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign unev </span><span class="opn">(</span><span class="pln">op operands</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save unev</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign exp </span><span class="opn">(</span><span class="pln">op operator</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign
   continue </span><span class="opn">(</span><span class="pln">label ev-appl-did-operator</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span></pre></div>

<p>Upon returning from evaluating the operator subexpression, we proceed to
evaluate the operands of the combination and to accumulate the resulting
arguments in a list, held in <code>argl</code>.  First we restore the unevaluated
operands and the environment.  We initialize <code>argl</code> to an empty list.
Then we assign to the <code>proc</code> register the procedure that was produced by
evaluating the operator.  If there are no operands, we go directly to
<code>apply-dispatch</code>.  Otherwise we save <code>proc</code> on the stack and start
the argument-evaluation loop:<a class="footnote_link" id="DOCF307" href="#FOOT307"><sup>307</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-appl-did-operator
  </span><span class="opn">(</span><span class="pln">restore unev</span><span class="clo">)</span><span class="pln">             </span><span class="roman"><span class="com">; the operands</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl </span><span class="opn">(</span><span class="pln">op empty-arglist</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign proc </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">    </span><span class="roman"><span class="com">; the operator</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op no-operands?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label apply-dispatch</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save proc</span><span class="clo">)</span></pre></div>

<p>Each cycle of the argument-evaluation loop evaluates an operand from the list
in <code>unev</code> and accumulates the result into <code>argl</code>.  To evaluate an
operand, we place it in the <code>exp</code> register and go to <code>eval-dispatch</code>,
after setting <code>continue</code> so that execution will resume with the
argument-accumulation phase.  But first we save the arguments accumulated so
far (held in <code>argl</code>), the environment (held in <code>env</code>), and the
remaining operands to be evaluated (held in <code>unev</code>).  A special case is
made for the evaluation of the last operand, which is handled at
<code>ev-appl-last-arg</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-appl-operand-loop
  </span><span class="opn">(</span><span class="pln">save argl</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign exp
          </span><span class="opn">(</span><span class="pln">op first-operand</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op last-operand?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-appl-last-arg</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save unev</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign continue 
          </span><span class="opn">(</span><span class="pln">label ev-appl-accumulate-arg</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span></pre></div>

<p>When an operand has been evaluated, the value is accumulated into the list held
in <code>argl</code>.  The operand is then removed from the list of unevaluated
operands in <code>unev</code>, and the argument-evaluation continues.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-appl-accumulate-arg
  </span><span class="opn">(</span><span class="pln">restore unev</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore argl</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl 
          </span><span class="opn">(</span><span class="pln">op adjoin-arg</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign unev
          </span><span class="opn">(</span><span class="pln">op rest-operands</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label ev-appl-operand-loop</span><span class="clo">))</span></pre></div>

<p>Evaluation of the last argument is handled differently.  There is no need to
save the environment or the list of unevaluated operands before going to
<code>eval-dispatch</code>, since they will not be required after the last operand is
evaluated.  Thus, we return from the evaluation to a special entry point
<code>ev-appl-accum-last-arg</code>, which restores the argument list, accumulates
the new argument, restores the saved procedure, and goes off to perform the
application.<a class="footnote_link" id="DOCF308" href="#FOOT308"><sup>308</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-appl-last-arg
  </span><span class="opn">(</span><span class="pln">assign continue 
          </span><span class="opn">(</span><span class="pln">label ev-appl-accum-last-arg</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span><span class="pln">
ev-appl-accum-last-arg
  </span><span class="opn">(</span><span class="pln">restore argl</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign argl 
          </span><span class="opn">(</span><span class="pln">op adjoin-arg</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore proc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label apply-dispatch</span><span class="clo">))</span></pre></div>

<p>The details of the argument-evaluation loop determine the order in which the
interpreter evaluates the operands of a combination (e.g., left to right or
right to left—see <a href="3_002e1.xhtml#Exercise-3_002e8">Exercise 3.8</a>).  This order is not determined by the
metacircular evaluator, which inherits its control structure from the
underlying Scheme in which it is implemented.<a class="footnote_link" id="DOCF309" href="#FOOT309"><sup>309</sup></a> Because
the <code>first-operand</code> selector (used in <code>ev-appl-operand-loop</code> to
extract successive operands from <code>unev</code>) is implemented as <code>car</code> and
the <code>rest-operands</code> selector is implemented as <code>cdr</code>, the
explicit-control evaluator will evaluate the operands of a combination in
left-to-right order.
</p>
<a id="Procedure-application"></a>
<h5 class="subsubheading">Procedure application</h5>

<p>The entry point <code>apply-dispatch</code> corresponds to the <code>apply</code> procedure
of the metacircular evaluator.  By the time we get to <code>apply-dispatch</code>,
the <code>proc</code> register contains the procedure to apply and <code>argl</code>
contains the list of evaluated arguments to which it must be applied.  The
saved value of <code>continue</code> (originally passed to <code>eval-dispatch</code> and
saved at <code>ev-application</code>), which tells where to return with the result of
the procedure application, is on the stack.  When the application is complete,
the controller transfers to the entry point specified by the saved
<code>continue</code>, with the result of the application in <code>val</code>.  As with the
metacircular <code>apply</code>, there are two cases to consider.  Either the
procedure to be applied is a primitive or it is a compound procedure.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">apply-dispatch
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op primitive-procedure?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label primitive-apply</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op compound-procedure?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label compound-apply</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label unknown-procedure-type</span><span class="clo">))</span></pre></div>

<p>We assume that each primitive is implemented so as to obtain its arguments from
<code>argl</code> and place its result in <code>val</code>.  To specify how the machine
handles primitives, we would have to provide a sequence of controller
instructions to implement each primitive and arrange for <code>primitive-apply</code>
to dispatch to the instructions for the primitive identified by the contents of
<code>proc</code>.  Since we are interested in the structure of the evaluation
process rather than the details of the primitives, we will instead just use an
<code>apply-primitive-procedure</code> operation that applies the procedure in
<code>proc</code> to the arguments in <code>argl</code>.  For the purpose of simulating the
evaluator with the simulator of <a href="5_002e2.xhtml#g_t5_002e2">5.2</a> we use the procedure
<code>apply-primitive-procedure</code>, which calls on the underlying Scheme system
to perform the application, just as we did for the metacircular evaluator in
<a href="4_002e1.xhtml#g_t4_002e1_002e4">4.1.4</a>.  After computing the value of the primitive application,
we restore <code>continue</code> and go to the designated entry point.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">primitive-apply
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">op apply-primitive-procedure</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span></pre></div>

<p>To apply a compound procedure, we proceed just as with the metacircular
evaluator.  We construct a frame that binds the procedure’s parameters to the
arguments, use this frame to extend the environment carried by the procedure,
and evaluate in this extended environment the sequence of expressions that
forms the body of the procedure.  <code>Ev-sequence</code>, described below in
<a href="#g_t5_002e4_002e2">5.4.2</a>, handles the evaluation of the sequence.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">compound-apply
  </span><span class="opn">(</span><span class="pln">assign unev 
          </span><span class="opn">(</span><span class="pln">op procedure-parameters</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign env
          </span><span class="opn">(</span><span class="pln">op procedure-environment</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign env
          </span><span class="opn">(</span><span class="pln">op extend-environment</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg argl</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign unev
          </span><span class="opn">(</span><span class="pln">op procedure-body</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg proc</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label ev-sequence</span><span class="clo">))</span></pre></div>

<p><code>Compound-apply</code> is the only place in the interpreter where the <code>env</code>
register is ever assigned a new value.  Just as in the metacircular evaluator,
the new environment is constructed from the environment carried by the
procedure, together with the argument list and the corresponding list of
variables to be bound.
</p>
<a id="g_t5_002e4_002e2"></a>
<a id="Sequence-Evaluation-and-Tail-Recursion"></a>
<h4 class="subsection"><span class="secnum">5.4.2</span><span class="sectitle">Sequence Evaluation and Tail Recursion</span></h4>

<p>The portion of the explicit-control evaluator at <code>ev-sequence</code> is
analogous to the metacircular evaluator’s <code>eval-sequence</code> procedure.  It
handles sequences of expressions in procedure bodies or in explicit
<code>begin</code> expressions.
</p>
<p>Explicit <code>begin</code> expressions are evaluated by placing the sequence of
expressions to be evaluated in <code>unev</code>, saving <code>continue</code> on the
stack, and jumping to <code>ev-sequence</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-begin
  </span><span class="opn">(</span><span class="pln">assign unev
          </span><span class="opn">(</span><span class="pln">op begin-actions</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label ev-sequence</span><span class="clo">))</span></pre></div>

<p>The implicit sequences in procedure bodies are handled by jumping to
<code>ev-sequence</code> from <code>compound-apply</code>, at which point <code>continue</code>
is already on the stack, having been saved at <code>ev-application</code>.
</p>
<p>The entries at <code>ev-sequence</code> and <code>ev-sequence-continue</code> form a loop
that successively evaluates each expression in a sequence.  The list of
unevaluated expressions is kept in <code>unev</code>.  Before evaluating each
expression, we check to see if there are additional expressions to be evaluated
in the sequence.  If so, we save the rest of the unevaluated expressions (held
in <code>unev</code>) and the environment in which these must be evaluated (held in
<code>env</code>) and call <code>eval-dispatch</code> to evaluate the expression.  The two
saved registers are restored upon the return from this evaluation, at
<code>ev-sequence-continue</code>.
</p>
<p>The final expression in the sequence is handled differently, at the entry point
<code>ev-sequence-last-exp</code>.  Since there are no more expressions to be
evaluated after this one, we need not save <code>unev</code> or <code>env</code> before
going to <code>eval-dispatch</code>.  The value of the whole sequence is the value of
the last expression, so after the evaluation of the last expression there is
nothing left to do except continue at the entry point currently held on the
stack (which was saved by <code>ev-application</code> or <code>ev-begin</code>.)  Rather
than setting up <code>continue</code> to arrange for <code>eval-dispatch</code> to return
here and then restoring <code>continue</code> from the stack and continuing at that
entry point, we restore <code>continue</code> from the stack before going to
<code>eval-dispatch</code>, so that <code>eval-dispatch</code> will continue at that entry
point after evaluating the expression.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-sequence
  </span><span class="opn">(</span><span class="pln">assign exp </span><span class="opn">(</span><span class="pln">op first-exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op last-exp?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-sequence-last-exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save unev</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign continue
          </span><span class="opn">(</span><span class="pln">label ev-sequence-continue</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span><span class="pln">
ev-sequence-continue
  </span><span class="opn">(</span><span class="pln">restore env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore unev</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign unev
          </span><span class="opn">(</span><span class="pln">op rest-exps</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label ev-sequence</span><span class="clo">))</span><span class="pln">
ev-sequence-last-exp
  </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span></pre></div>

<a id="Tail-recursion"></a>
<h5 class="subsubheading">Tail recursion</h5>

<p>In <a href="Chapter-1.xhtml#Chapter-1">Chapter 1</a> we said that the process described by a procedure such as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt-iter guess x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">good-enough? guess x</span><span class="clo">)</span><span class="pln">
      guess
      </span><span class="opn">(</span><span class="pln">sqrt-iter </span><span class="opn">(</span><span class="pln">improve guess x</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">)))</span></pre></div>

<p>is an iterative process.  Even though the procedure is syntactically recursive
(defined in terms of itself), it is not logically necessary for an evaluator to
save information in passing from one call to <code>sqrt-iter</code> to the
next.<a class="footnote_link" id="DOCF310" href="#FOOT310"><sup>310</sup></a> An evaluator that can execute a procedure such as
<code>sqrt-iter</code> without requiring increasing storage as the procedure
continues to call itself is called a <a id="index-tail_002drecursive-1"></a>
<em>tail-recursive</em> evaluator.  The
metacircular implementation of the evaluator in <a href="Chapter-4.xhtml#Chapter-4">Chapter 4</a> does not
specify whether the evaluator is tail-recursive, because that evaluator
inherits its mechanism for saving state from the underlying Scheme.  With the
explicit-control evaluator, however, we can trace through the evaluation
process to see when procedure calls cause a net accumulation of information on
the stack.
</p>
<p>Our evaluator is tail-recursive, because in order to evaluate the final
expression of a sequence we transfer directly to <code>eval-dispatch</code> without
saving any information on the stack.  Hence, evaluating the final expression in
a sequence—even if it is a procedure call (as in <code>sqrt-iter</code>, where the
<code>if</code> expression, which is the last expression in the procedure body,
reduces to a call to <code>sqrt-iter</code>)—will not cause any information to be
accumulated on the stack.<a class="footnote_link" id="DOCF311" href="#FOOT311"><sup>311</sup></a>
</p>
<p>If we did not think to take advantage of the fact that it was unnecessary to
save information in this case, we might have implemented <code>eval-sequence</code>
by treating all the expressions in a sequence in the same way—saving the
registers, evaluating the expression, returning to restore the registers, and
repeating this until all the expressions have been evaluated:<a class="footnote_link" id="DOCF312" href="#FOOT312"><sup>312</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-sequence
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op no-more-exps?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-sequence-end</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign exp </span><span class="opn">(</span><span class="pln">op first-exp</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save unev</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign continue
          </span><span class="opn">(</span><span class="pln">label ev-sequence-continue</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span><span class="pln">
ev-sequence-continue
  </span><span class="opn">(</span><span class="pln">restore env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore unev</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign unev </span><span class="opn">(</span><span class="pln">op rest-exps</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label ev-sequence</span><span class="clo">))</span><span class="pln">
ev-sequence-end
  </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span></pre></div>

<p>This may seem like a minor change to our previous code for evaluation of a
sequence: The only difference is that we go through the save-restore cycle for
the last expression in a sequence as well as for the others.  The interpreter
will still give the same value for any expression.  But this change is fatal to
the tail-recursive implementation, because we must now return after evaluating
the final expression in a sequence in order to undo the (useless) register
saves.  These extra saves will accumulate during a nest of procedure calls.
Consequently, processes such as <code>sqrt-iter</code> will require space
proportional to the number of iterations rather than requiring constant space.
This difference can be significant.  For example, with tail recursion, an
infinite loop can be expressed using only the procedure-call mechanism:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">display n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">count </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)))</span></pre></div>

<p>Without tail recursion, such a procedure would eventually run out of stack
space, and expressing a true iteration would require some control mechanism
other than procedure call.
</p>
<a id="g_t5_002e4_002e3"></a>
<a id="Conditionals_002c-Assignments_002c-and-Definitions"></a>
<h4 class="subsection"><span class="secnum">5.4.3</span><span class="sectitle">Conditionals, Assignments, and Definitions</span></h4>

<p>As with the metacircular evaluator, special forms are handled by selectively
evaluating fragments of the expression.  For an <code>if</code> expression, we must
evaluate the predicate and decide, based on the value of predicate, whether to
evaluate the consequent or the alternative.
</p>
<p>Before evaluating the predicate, we save the <code>if</code> expression itself so
that we can later extract the consequent or alternative.  We also save the
environment, which we will need later in order to evaluate the consequent or
the alternative, and we save <code>continue</code>, which we will need later in order
to return to the evaluation of the expression that is waiting for the value of
the <code>if</code>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-if
  </span><span class="opn">(</span><span class="pln">save exp</span><span class="clo">)</span><span class="pln">   </span><span class="roman"><span class="com">; save expression for later</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label ev-if-decide</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign exp </span><span class="opn">(</span><span class="pln">op if-predicate</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="roman"><span class="com">; evaluate the predicate:</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span><span class="pln">  </span></pre></div>

<p>When we return from evaluating the predicate, we test whether it was true or
false and, depending on the result, place either the consequent or the
alternative in <code>exp</code> before going to <code>eval-dispatch</code>.  Notice that
restoring <code>env</code> and <code>continue</code> here sets up <code>eval-dispatch</code> to
have the correct environment and to continue at the right place to receive the
value of the <code>if</code> expression.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-if-decide
  </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore exp</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op true?</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ev-if-consequent</span><span class="clo">))</span><span class="pln">
ev-if-alternative
  </span><span class="opn">(</span><span class="pln">assign exp </span><span class="opn">(</span><span class="pln">op if-alternative</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span><span class="pln">
ev-if-consequent
  </span><span class="opn">(</span><span class="pln">assign exp </span><span class="opn">(</span><span class="pln">op if-consequent</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span></pre></div>

<a id="Assignments-and-definitions-1"></a>
<h5 class="subsubheading">Assignments and definitions</h5>

<p>Assignments are handled by <code>ev-assignment</code>, which is reached from
<code>eval-dispatch</code> with the assignment expression in <code>exp</code>.  The code at
<code>ev-assignment</code> first evaluates the value part of the expression and then
installs the new value in the environment.  <code>Set-variable-value!</code> is
assumed to be available as a machine operation.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-assignment
  </span><span class="opn">(</span><span class="pln">assign unev 
          </span><span class="opn">(</span><span class="pln">op assignment-variable</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save unev</span><span class="clo">)</span><span class="pln">   </span><span class="roman"><span class="com">; save variable for later</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign exp
          </span><span class="opn">(</span><span class="pln">op assignment-value</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign continue
          </span><span class="opn">(</span><span class="pln">label ev-assignment-1</span><span class="clo">))</span><span class="pln">
  </span><span class="roman"><span class="com">; evaluate the assignment value:</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span><span class="pln">  
ev-assignment-1
  </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore unev</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op set-variable-value!</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val
          </span><span class="opn">(</span><span class="pln">const ok</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span></pre></div>

<p>Definitions are handled in a similar way:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">ev-definition
  </span><span class="opn">(</span><span class="pln">assign unev 
          </span><span class="opn">(</span><span class="pln">op definition-variable</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save unev</span><span class="clo">)</span><span class="pln">   </span><span class="roman"><span class="com">; save variable for later</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign exp 
          </span><span class="opn">(</span><span class="pln">op definition-value</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">reg exp</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">save continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label ev-definition-1</span><span class="clo">))</span><span class="pln">
  </span><span class="roman"><span class="com">; evaluate the definition value:</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span><span class="pln">  
ev-definition-1
  </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore env</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore unev</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op define-variable!</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg unev</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg env</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign val </span><span class="opn">(</span><span class="pln">const ok</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-5_002e23"></a>Exercise 5.23:</strong> Extend the evaluator to handle
derived expressions such as <code>cond</code>, <code>let</code>, and so on 
(<a href="4_002e1.xhtml#g_t4_002e1_002e2">4.1.2</a>).  You may “cheat” and assume that the syntax transformers such
as <code>cond-&gt;if</code> are available as machine operations.<a class="footnote_link" id="DOCF313" href="#FOOT313"><sup>313</sup></a>
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e24"></a>Exercise 5.24:</strong> Implement <code>cond</code> as a new
basic special form without reducing it to <code>if</code>.  You will have to
construct a loop that tests the predicates of successive <code>cond</code> clauses
until you find one that is true, and then use <code>ev-sequence</code> to evaluate
the actions of the clause.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e25"></a>Exercise 5.25:</strong> Modify the evaluator so that it
uses normal-order evaluation, based on the lazy evaluator of <a href="4_002e2.xhtml#g_t4_002e2">4.2</a>.
</p></blockquote>

<a id="g_t5_002e4_002e4"></a>
<a id="Running-the-Evaluator"></a>
<h4 class="subsection"><span class="secnum">5.4.4</span><span class="sectitle">Running the Evaluator</span></h4>

<p>With the implementation of the explicit-control evaluator we come to the end of
a development, begun in <a href="Chapter-1.xhtml#Chapter-1">Chapter 1</a>, in which we have explored successively
more precise models of the evaluation process.  We started with the relatively
informal substitution model, then extended this in <a href="Chapter-3.xhtml#Chapter-3">Chapter 3</a> to the
environment model, which enabled us to deal with state and change.  In the
metacircular evaluator of <a href="Chapter-4.xhtml#Chapter-4">Chapter 4</a>, we used Scheme itself as a language
for making more explicit the environment structure constructed during
evaluation of an expression.  Now, with register machines, we have taken a
close look at the evaluator’s mechanisms for storage management, argument
passing, and control.  At each new level of description, we have had to raise
issues and resolve ambiguities that were not apparent at the previous, less
precise treatment of evaluation.  To understand the behavior of the
explicit-control evaluator, we can simulate it and monitor its performance.
</p>
<p>We will install a driver loop in our evaluator machine.  This plays the role of
the <code>driver-loop</code> procedure of <a href="4_002e1.xhtml#g_t4_002e1_002e4">4.1.4</a>.  The evaluator will
repeatedly print a prompt, read an expression, evaluate the expression by going
to <code>eval-dispatch</code>, and print the result.  The following instructions form
the beginning of the explicit-control evaluator’s controller
sequence:<a class="footnote_link" id="DOCF314" href="#FOOT314"><sup>314</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">read-eval-print-loop
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op initialize-stack</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op prompt-for-input</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">const </span><span class="str">";;; EC-Eval input:"</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign exp </span><span class="opn">(</span><span class="pln">op read</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign env </span><span class="opn">(</span><span class="pln">op get-global-environment</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label print-result</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label eval-dispatch</span><span class="clo">))</span><span class="pln">
print-result
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op announce-output</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">const </span><span class="str">";;; EC-Eval value:"</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op user-print</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label read-eval-print-loop</span><span class="clo">))</span></pre></div>

<p>When we encounter an error in a procedure (such as the “unknown procedure type
error” indicated at <code>apply-dispatch</code>), we print an error message and
return to the driver loop.<a class="footnote_link" id="DOCF315" href="#FOOT315"><sup>315</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">unknown-expression-type
  </span><span class="opn">(</span><span class="pln">assign 
   val
   </span><span class="opn">(</span><span class="pln">const unknown-expression-type-error</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label signal-error</span><span class="clo">))</span><span class="pln">
unknown-procedure-type
  </span><span class="roman"><span class="com">; clean up stack (from </span><code><span class="com">apply-dispatch</span></code><span class="com">):</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">    
  </span><span class="opn">(</span><span class="pln">assign 
   val
   </span><span class="opn">(</span><span class="pln">const unknown-procedure-type-error</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label signal-error</span><span class="clo">))</span><span class="pln">
signal-error
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op user-print</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label read-eval-print-loop</span><span class="clo">))</span></pre></div>

<p>For the purposes of the simulation, we initialize the stack each time through
the driver loop, since it might not be empty after an error (such as an
undefined variable) interrupts an evaluation.<a class="footnote_link" id="DOCF316" href="#FOOT316"><sup>316</sup></a>
</p>
<p>If we combine all the code fragments presented in 
<a href="#g_t5_002e4_002e1">5.4.1</a>–<a href="#g_t5_002e4_002e4">5.4.4</a>, we can create an evaluator machine model that we can
run using the register-machine simulator of <a href="5_002e2.xhtml#g_t5_002e2">5.2</a>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> eceval
  </span><span class="opn">(</span><span class="pln">make-machine
   </span><span class="lit">'</span><span class="opn">(</span><span class="pln">exp env val proc argl continue unev</span><span class="clo">)</span><span class="pln">
   eceval-operations
   </span><span class="lit">'</span><span class="opn">(</span><span class="pln">read-eval-print-loop
     ⟨</span><em><span class="pln">entire machine controller</span></em><span class="pln"> 
      </span><em><span class="pln">as given above</span></em><span class="pln">⟩</span><span class="clo">)))</span></pre></div>

<p>We must define Scheme procedures to simulate the operations used as primitives
by the evaluator.  These are the same procedures we used for the metacircular
evaluator in <a href="4_002e1.xhtml#g_t4_002e1">4.1</a>, together with the few additional ones defined
in footnotes throughout <a href="#g_t5_002e4">5.4</a>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> eceval-operations
  </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">list </span><span class="lit">'self-evaluating?</span><span class="pln"> 
              self-evaluating</span><span class="clo">)</span><span class="pln">
        ⟨</span><em><span class="pln">complete list of operations</span></em><span class="pln"> 
         </span><em><span class="pln">for eceval machine</span></em><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>Finally, we can initialize the global environment and run the evaluator:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> the-global-environment
  </span><span class="opn">(</span><span class="pln">setup-environment</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">start eceval</span><span class="clo">)</span><span class="pln">

</span><i><span class="com">;;; EC-Eval input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? x</span><span class="clo">)</span><span class="pln">
      y
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">append </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> y</span><span class="clo">))))</span><span class="pln">

</span><i><span class="com">;;; EC-Eval value:</span></i><span class="pln">
</span><i><span class="pln">ok</span></i><span class="pln">

</span><i><span class="com">;;; EC-Eval input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">append </span><span class="lit">'</span><span class="opn">(</span><span class="pln">a b c</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">d e f</span><span class="clo">))</span><span class="pln">

</span><i><span class="com">;;; EC-Eval value:</span></i><span class="pln">
</span><i><span class="opn">(</span><span class="pln">a b c d e f</span><span class="clo">)</span></i>
</pre></div>

<p>Of course, evaluating expressions in this way will take much longer than if we
had directly typed them into Scheme, because of the multiple levels of
simulation involved.  Our expressions are evaluated by the
explicit-control-evaluator machine, which is being simulated by a Scheme
program, which is itself being evaluated by the Scheme interpreter.
</p>
<a id="Monitoring-the-performance-of-the-evaluator"></a>
<h5 class="subsubheading">Monitoring the performance of the evaluator</h5>

<p>Simulation can be a powerful tool to guide the implementation of evaluators.
Simulations make it easy not only to explore variations of the register-machine
design but also to monitor the performance of the simulated evaluator.  For
example, one important factor in performance is how efficiently the evaluator
uses the stack.  We can observe the number of stack operations required to
evaluate various expressions by defining the evaluator register machine with
the version of the simulator that collects statistics on stack use 
(<a href="5_002e2.xhtml#g_t5_002e2_002e4">5.2.4</a>), and adding an instruction at the evaluator’s <code>print-result</code>
entry point to print the statistics:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">print-result
  </span><span class="roman"><span class="com">; added instruction:</span></span><span class="pln">
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op print-stack-statistics</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op announce-output</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">const </span><span class="str">";;; EC-Eval value:"</span><span class="clo">))</span><span class="pln">
  </span><span class="roman"><span class="pun">…</span></span><span class="pln"> </span><span class="roman"><span class="com">; same as before</span></span>
</pre></div>

<p>Interactions with the evaluator now look like this:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><i><span class="com">;;; EC-Eval input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> n</span><span class="clo">)))</span><span class="pln">
</span><i><span class="opn">(</span><span class="pln">total-pushes </span><span class="pun">=</span><span class="pln"> </span><span class="lit">3</span><span class="pun">,</span><span class="pln"> maximum-depth </span><span class="pun">=</span><span class="pln"> </span><span class="lit">3</span><span class="clo">)</span></i><span class="pln">

</span><i><span class="com">;;; EC-Eval value:</span></i><span class="pln">
</span><i><span class="pln">ok</span></i><span class="pln">

</span><i><span class="com">;;; EC-Eval input:</span></i><span class="pln">
</span><span class="opn">(</span><span class="pln">factorial </span><span class="lit">5</span><span class="clo">)</span><span class="pln">
</span><i><span class="opn">(</span><span class="pln">total-pushes </span><span class="pun">=</span><span class="pln"> </span><span class="lit">144</span><span class="pun">,</span><span class="pln"> maximum-depth </span><span class="pun">=</span><span class="pln"> </span><span class="lit">28</span><span class="clo">)</span></i><span class="pln">

</span><i><span class="com">;;; EC-Eval value:</span></i><span class="pln">
</span><i><span class="lit">120</span></i>
</pre></div>

<p>Note that the driver loop of the evaluator reinitializes the stack at the start
of each interaction, so that the statistics printed will refer only to stack
operations used to evaluate the previous expression.
</p>
<blockquote>
<p><strong><a id="Exercise-5_002e26"></a>Exercise 5.26:</strong> Use the monitored stack to
explore the tail-recursive property of the evaluator (<a href="#g_t5_002e4_002e2">5.4.2</a>).
Start the evaluator and define the iterative <code>factorial</code> procedure from
<a href="1_002e2.xhtml#g_t1_002e2_002e1">1.2.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter product counter</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> counter n</span><span class="clo">)</span><span class="pln">
        product
        </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> counter product</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> counter </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span></pre></div>

<p>Run the procedure with some small values of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  Record the maximum stack
depth and the number of pushes required to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math> for each of these
values.
</p>
<ol>
<li> You will find that the maximum depth required to evaluate <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math> is independent
of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  What is that depth?

</li><li> Determine from your data a formula in terms of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> for the total number of
push operations used in evaluating <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math> for any <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>≥<!-- ≥ --></mo>
    <mn>1</mn>
  </mrow>
</math>.  Note that the
number of operations used is a linear function of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> and is thus determined
by two constants.

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e27"></a>Exercise 5.27:</strong> For comparison with <a href="#Exercise-5_002e26">Exercise 5.26</a>, 
explore the behavior of the following procedure for computing factorials
recursively:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">1</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> n</span><span class="clo">)))</span></pre></div>

<p>By running this procedure with the monitored stack, determine, as a function of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, the maximum depth of the stack and the total number of pushes used in
evaluating <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math> for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>≥<!-- ≥ --></mo>
    <mn>1</mn>
  </mrow>
</math>.  (Again, these functions will be linear.)
Summarize your experiments by filling in the following table with the
appropriate expressions in terms of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>:
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="left left left" rowspacing="4pt" columnspacing="1em" rowlines="none solid none solid none" columnlines="solid solid">
    <mtr>
      <mtd/>
      <mtd>
        <mtext>Maximum</mtext>
      </mtd>
      <mtd>
        <mtext>Number of</mtext>
      </mtd>
    </mtr>
    <mtr>
      <mtd/>
      <mtd>
        <mtext>depth</mtext>
      </mtd>
      <mtd>
        <mtext>pushes</mtext>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mtext>Recursive</mtext>
      </mtd>
      <mtd/>
      <mtd/>
    </mtr>
    <mtr>
      <mtd>
        <mtext>factorial</mtext>
      </mtd>
      <mtd/>
      <mtd/>
    </mtr>
    <mtr>
      <mtd>
        <mtext>Iterative</mtext>
      </mtd>
      <mtd/>
      <mtd/>
    </mtr>
    <mtr>
      <mtd>
        <mtext>factorial</mtext>
      </mtd>
      <mtd/>
      <mtd/>
    </mtr>
  </mtable>
</math>
The maximum depth is a measure of the amount of space used by the evaluator in
carrying out the computation, and the number of pushes correlates well with the
time required.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e28"></a>Exercise 5.28:</strong> Modify the definition of the
evaluator by changing <code>eval-sequence</code> as described in <a href="#g_t5_002e4_002e2">5.4.2</a>
so that the evaluator is no longer tail-recursive.  Rerun your experiments from
<a href="#Exercise-5_002e26">Exercise 5.26</a> and <a href="#Exercise-5_002e27">Exercise 5.27</a> to demonstrate that both versions
of the <code>factorial</code> procedure now require space that grows linearly with
their input.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e29"></a>Exercise 5.29:</strong> Monitor the stack operations in
the tree-recursive Fibonacci computation:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> n </span><span class="lit">2</span><span class="clo">)</span><span class="pln">
      n
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">2</span><span class="clo">)))))</span></pre></div>

<ol>
<li> Give a formula in terms of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> for the maximum depth of the stack required to
compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>≥<!-- ≥ --></mo>
    <mn>2</mn>
  </mrow>
</math>.  Hint: In <a href="1_002e2.xhtml#g_t1_002e2_002e2">1.2.2</a> we
argued that the space used by this process grows linearly with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.

</li><li> Give a formula for the total number of pushes used to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>
for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>≥<!-- ≥ --></mo>
    <mn>2</mn>
  </mrow>
</math>.  You should find that the number of pushes (which correlates
well with the time used) grows exponentially with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  Hint: Let
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> be the number of pushes used in computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  You
should be able to argue that there is a formula that expresses <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> in
terms of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>2</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, and some fixed “overhead”
constant <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math> that is independent of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  Give the formula, and say what
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math> is.  Then show that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> can be expressed as 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>+</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mo>+</mo>
    <mi>b</mi>
  </mrow>
</math> and give the values of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>.

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e30"></a>Exercise 5.30:</strong> Our evaluator currently catches
and signals only two kinds of errors—unknown expression types and unknown
procedure types.  Other errors will take us out of the evaluator
read-eval-print loop.  When we run the evaluator using the register-machine
simulator, these errors are caught by the underlying Scheme system.  This is
analogous to the computer crashing when a user program makes an
error.<a class="footnote_link" id="DOCF317" href="#FOOT317"><sup>317</sup></a>  It is a
large project to make a real error system work, but it is well worth the effort
to understand what is involved here.
</p>
<ol>
<li> Errors that occur in the evaluation process, such as an attempt to access an
unbound variable, could be caught by changing the lookup operation to make it
return a distinguished condition code, which cannot be a possible value of any
user variable.  The evaluator can test for this condition code and then do what
is necessary to go to <code>signal-error</code>.  Find all of the places in the
evaluator where such a change is necessary and fix them.  This is lots of work.

</li><li> Much worse is the problem of handling errors that are signaled by applying
primitive procedures, such as an attempt to divide by zero or an attempt to
extract the <code>car</code> of a symbol.  In a professionally written high-quality
system, each primitive application is checked for safety as part of the
primitive.  For example, every call to <code>car</code> could first check that the
argument is a pair.  If the argument is not a pair, the application would
return a distinguished condition code to the evaluator, which would then report
the failure.  We could arrange for this in our register-machine simulator by
making each primitive procedure check for applicability and returning an
appropriate distinguished condition code on failure. Then the
<code>primitive-apply</code> code in the evaluator can check for the condition code
and go to <code>signal-error</code> if necessary.  Build this structure and make it
work.  This is a major project.

</li></ol>
</blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT304"><p><a class="footnote_backlink" href="#DOCF304"><sup>304</sup></a>
See <a href="References.xhtml#Batali-et-al_002e-1982">Batali et al. 1982</a> for more information
on the chip and the method by which it was designed.</p>
</div>
<div id="FOOT305"><p><a class="footnote_backlink" href="#DOCF305"><sup>305</sup></a>
In
our controller, the dispatch is written as a sequence of <code>test</code> and
<code>branch</code> instructions.  Alternatively, it could have been written in a
data-directed style (and in a real system it probably would have been) to avoid
the need to perform sequential tests and to facilitate the definition of new
expression types.  A machine designed to run Lisp would probably include a
<code>dispatch-on-type</code> instruction that would efficiently execute such
data-directed dispatches.</p>
</div>
<div id="FOOT306"><p><a class="footnote_backlink" href="#DOCF306"><sup>306</sup></a>
This is an
important but subtle point in translating algorithms from a procedural
language, such as Lisp, to a register-machine language.  As an alternative to
saving only what is needed, we could save all the registers (except <code>val</code>)
before each recursive call. This is called a <a id="index-framed_002dstack"></a>
<em>framed-stack</em> discipline.
This would work but might save more registers than necessary; this could be an
important consideration in a system where stack operations are expensive.
Saving registers whose contents will not be needed later may also hold onto
useless data that could otherwise be garbage-collected, freeing space to be
reused.</p>
</div>
<div id="FOOT307"><p><a class="footnote_backlink" href="#DOCF307"><sup>307</sup></a>
We add to the evaluator data-structure
procedures in <a href="4_002e1.xhtml#g_t4_002e1_002e3">4.1.3</a> the following two procedures for manipulating
argument lists:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-arglist</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">adjoin-arg arg arglist</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">append arglist </span><span class="opn">(</span><span class="pln">list arg</span><span class="clo">)))</span></pre></div>

<p>We also use an additional syntax procedure to test for the last operand in a
combination:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">last-operand? ops</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> ops</span><span class="clo">)))</span></pre></div>
</div>
<div id="FOOT308"><p><a class="footnote_backlink" href="#DOCF308"><sup>308</sup></a>
The optimization of treating the last operand specially
is known as <a id="index-evlis-tail-recursion"></a>
<em>evlis tail recursion</em> (see <a href="References.xhtml#Wand-1980">Wand 1980</a>).  We could be
somewhat more efficient in the argument evaluation loop if we made evaluation
of the first operand a special case too.  This would permit us to postpone
initializing <code>argl</code> until after evaluating the first operand, so as to
avoid saving <code>argl</code> in this case.  The compiler in <a href="5_002e5.xhtml#g_t5_002e5">5.5</a>
performs this optimization.  (Compare the <code>construct-arglist</code> procedure of
<a href="5_002e5.xhtml#g_t5_002e5_002e3">5.5.3</a>.)</p>
</div>
<div id="FOOT309"><p><a class="footnote_backlink" href="#DOCF309"><sup>309</sup></a>
The order of operand
evaluation in the metacircular evaluator is determined by the order of
evaluation of the arguments to <code>cons</code> in the procedure
<code>list-of-values</code> of <a href="4_002e1.xhtml#g_t4_002e1_002e1">4.1.1</a> (see <a href="4_002e1.xhtml#Exercise-4_002e1">Exercise 4.1</a>).</p>
</div>
<div id="FOOT310"><p><a class="footnote_backlink" href="#DOCF310"><sup>310</sup></a>
We saw in <a href="5_002e1.xhtml#g_t5_002e1">5.1</a> how to implement such a process with
a register machine that had no stack; the state of the process was stored in a
fixed set of registers.</p>
</div>
<div id="FOOT311"><p><a class="footnote_backlink" href="#DOCF311"><sup>311</sup></a>
This implementation of tail recursion in
<code>ev-sequence</code> is one variety of a well-known optimization technique used
by many compilers.  In compiling a procedure that ends with a procedure call,
one can replace the call by a jump to the called procedure’s entry point.
Building this strategy into the interpreter, as we have done in this section,
provides the optimization uniformly throughout the language.</p>
</div>
<div id="FOOT312"><p><a class="footnote_backlink" href="#DOCF312"><sup>312</sup></a>
We can
define <code>no-more-exps?</code> as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">no-more-exps? seq</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">null? seq</span><span class="clo">))</span></pre></div>
</div>
<div id="FOOT313"><p><a class="footnote_backlink" href="#DOCF313"><sup>313</sup></a>
This isn’t
really cheating.  In an actual implementation built from scratch, we would use
our explicit-control evaluator to interpret a Scheme program that performs
source-level transformations like <code>cond-&gt;if</code> in a syntax phase that runs
before execution.</p>
</div>
<div id="FOOT314"><p><a class="footnote_backlink" href="#DOCF314"><sup>314</sup></a>
We assume here that <code>read</code> and the various printing
operations are available as primitive machine operations, which is useful for
our simulation, but completely unrealistic in practice.  These are actually
extremely complex operations.  In practice, they would be implemented using
low-level input-output operations such as transferring single characters to and
from a device.
</p>
<p>To support the <code>get-global-environment</code> operation we define
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> the-global-environment
  </span><span class="opn">(</span><span class="pln">setup-environment</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">get-global-environment</span><span class="clo">)</span><span class="pln">
  the-global-environment</span><span class="clo">)</span></pre></div>
</div>
<div id="FOOT315"><p><a class="footnote_backlink" href="#DOCF315"><sup>315</sup></a>
There are other errors that we would like
the interpreter to handle, but these are not so simple.  See <a href="#Exercise-5_002e30">Exercise 5.30</a>.</p>
</div>
<div id="FOOT316"><p><a class="footnote_backlink" href="#DOCF316"><sup>316</sup></a>
We could perform the
stack initialization only after errors, but doing it in the driver loop will be
convenient for monitoring the evaluator’s performance, as described below.</p>
</div>
<div id="FOOT317"><p><a class="footnote_backlink" href="#DOCF317"><sup>317</sup></a>
Regrettably, this is the normal state of affairs in
conventional compiler-based language systems such as C.  In <abbr>UNIX</abbr>(tm)
the system “dumps core,” and in <abbr>DOS</abbr>/Windows(tm) it becomes
catatonic.  The Macintosh(tm) displays a picture of an exploding bomb and
offers you the opportunity to reboot the computer—if you’re lucky.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="5_002e5.xhtml#g_t5_002e5" accesskey="n" rel="next">5.5</a>, Prev: <a href="5_002e3.xhtml#g_t5_002e3" accesskey="p" rel="prev">5.3</a>, Up: <a href="#g_t5_002e4" accesskey="u" rel="prev">5.4</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>